【源头活水】DeepEMD : 小样本学习中的可微EMD

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

来源：知乎—胖虎

地址：https://zhuanlan.zhihu.com/p/410689118

目前小样本学习领域，度量学习依然是一大热门。大部分度量学习都是先用CNN提取图片特征，然后用一个距离度量函数（比如余弦距离，欧氏距离）进行分类。这些距离度量分类的方法直接在测试图片和训练图片的embedding上计算相似度，从而巧妙地避开了一个难点：小样本环境下优化一个分类器。然而，本文指出，一个理想的度量学习算法应该具备使用局部具有辨认性的特征的能力，以及防止被图片中无关的区域干扰的能力。

所以本文提出了使用Earth Mover's Distance来计算图片之间的相似度的方法。EMD最初被用于图片修复领域，简单来说就是optimal transport（最优运输）的一种方法。

论文：DeepEMD: Differentiable Earth Mover's Distance for Few-Shot Learning

https://arxiv.org/abs/2003.06777

代码：https://github.com/icoz69/DeepEMD

01

基础知识补充：Optimal Transport & Wasserstein Distance

Wasserstein Distance就是Earth Mover's Distance。

首先思考一个问题：假设有一个一维世界（一条线），上面有  个饭店，在直线上不同的位置  ，每个饭店分别有红烧肉  斤，恰好，又有  个饿鬼，在不同地方  ，都爱吃红烧肉。每个饿鬼分别想吃  斤。各个饭店和饿鬼之间的距离为  。假设这些饿鬼饿的走不动了，只能靠饿了么蓝骑士送过去。问：如何才能最高效地把这些饿鬼喂饱（或者说，怎么才能让蓝骑士最省力）？

分析问题：影响运输成本的因素有两个：运输距离、运输的红烧肉重量。所以我们优化的目标可以写作：

其中  是运输矩阵，  表示从饭店  送到饿鬼  的红烧肉重量。满足 , 。  表示从饭店  到饿鬼  的距离。距离是固定的（饭店不可能移动，饿鬼也饿的半死不活走不动了），所以我们最终目标是找到一个运输矩阵  ，使得运输成本最小。

如果只是为了阅读本文而临时补一下预备知识，那么读到这里就可以把下面一段跳过了，因为本文使用的就是离散状态下的EMD，但是为了知识的完备性，我下面还是把连续状态下的EMD写出来。另外，连续状态下的EMD在一些小样本领域的论文，甚至其他领域论文中都有用到。

现在把问题抽象化到连续函数上：

把  个饭店转化成随机变量  ，不同饭店的红烧肉库存量就是关于  的概率分布  。饿鬼就是  ，每个饿鬼的需求量就是关于  的概率分布  。这时候，原问题就变成了从  转化成  的最小代价：

这里的  就等同于上面的  ，只不过是在连续变量上，是一个联合概率密度。

02

Distance

从上面的公式，我们可以得到Optimal Transport Divergence的公式：

约束条件同上：

距离公式  可以自己选择合适的公式。如果将其定义为  ，那就得到了2-Wasserstein Distance:

由此可以推出k-Wasserstein Distance的公式：

然而这个公式想要去优化，复杂度非常高。比如一张  的binary图片，其复杂度为  。

03

Dual Form of OTD

OTD本质上也是一个线性规划问题，就和SVM一样。所以将其转换为dual form求解：

其中，

直观来说，这个dual form的意思就是  中找到某个  ，使得  在不同分布  ,   下期望值的差最大。显而易见，如果  ,   相同，  。通过求解对偶形，就可以对原最优运输问题求的最优解  。

04

Methods

本文使用N ways K shots描述法。

整体流程如上图中上半幅图所示，先support，query提取局部embedding，然后用EMD一通计算，得到距离，然后根据这个距离进行分类。典型的度量学习的流程。下面介绍细节。

05

EMD for FSC

如上面流程图的下半图所示，本文分别做了三组不同的实验，整张图直接用FCN，用网格分割图片，以及随机在图片中采样。具体实验结果见原文实验部分。经过特征提取，转化为embedding之后，根据EMD来计算距离。假设每个集中都有  个向量，假设任意两幅图的embedding nodes为  ， 则每个单位的cost的计算过程如下：

回忆高中向量知识，应该可以看出后面这项其实就是两个向量之间夹角的余弦。也就是说，如果两个nodes完全相同，那么夹角为  ，余弦值就是  。于是乎这个距离就是  。因此，越相似的nodes，产生的cost越小。这个  就对应之前的饭店到饿鬼的距离，也就是运输距离。

等到求出了最佳运输矩阵  ，也就是上面的EMD解释当中的  ，就可以计算两幅图的相似度了：

其中  是  中的项。

06

End-to-end Training

在机器学习中，经常会看到end-to-end training / learning（端到端学习），首先定义一下什么是端到端学习。Stackexchange上这篇回答解释的挺好，引用其中一小段：

https://dsp.stackexchange.com/questions/32191/when-is-a-network-called-end-to-end-training

End-to-end learning usually refers to omitting any hand-crafted intermediary algorithms and directly learning the solution of a given problem from the sampled dataset. This could involve concatenation of different networks such as multiple CNNs and LSTMs, which are trained simultaneously.

在本文的情境下，为了用端到端的方式求解最佳运输矩阵  ，  必须对  （模型参数）可微。在最优KKT条件下用隐函数定理就可以得到Jacobian。首先把原问题写成矩阵形式：

这里  是优化目标，其中  （也就是饭店数量乘饿鬼数量，或者在这个具体问题中，就是两张图片的feature总量相乘）。换句话说，这里  实际上就是把  拉长展平了。  是参数。  是运输距离矩阵。  表示  ，  表示以及（也就是上面EMD解释中的运输矩阵每一行的和等于一个饭店的红烧肉储备量，每一列的和表示一个饿鬼的红烧肉需求量）。

上面这个问题就是一个线性规划问题，所以在原objective function上加上两个拉格朗日算子：

其中  和  分别是上面的等式约束和不等式约束的对偶变量。接着根据KKT条件，就可以通过求解  。求得最优  ，其中：

大体框架就出来了。然后就有一个问题，上式中梯度怎么求？

定理1：假设  ，且其所有导数均存在，则  在  这一点上对于  的偏雅可比  为：

对  的偏雅可比可定义为：

因此，一旦得到了  的最优解，就可以  相对于  的梯度的解析解了。这样极大地提升了Backpropagation的效率。

07

Weight Generation

到目前为止，所有的讨论都是假设知道了权重的情况下。权重是什么？比如在上面的饭店饿鬼模型中，一个饿鬼的红烧肉需求量就是一个权重。如果某个饿鬼只要吃50克红烧肉，这么小的需求量对总EMD产生的影响微乎其微，就算叫一个很远的饭店给他送去也没多少影响。但是如果一个饿鬼想吃5公斤红烧肉，那就不得了了，如果饭店很远，送过来的cost会无比大，所以会尽量找附近的一些饭店给他拼拼凑凑地送过去。

所以对于本文的问题，应该如何确定一个两张图片之间合适的权重？在彩色图片修复领域，通常颜色越占主导地位，像素越多的nodes会得到越大的权重。但是在小样本领域，像素越多不一定能够反映越多信息，图片中包含了许多高级的语义信息。所以很自然地能想到，既然要提取语义信息，那就得区分前景和背景。相对来说，前景肯定包含更多语义信息，故而更重要。那么怎么找到前景？两张图片中共同出现的区域更可能是前景。于是本文提出了cross-reference mechanism（交叉参照原理）。假设  和  分别表示从两个特征映射中提出的两个向量：

这个分数非负。

最后，把分数归一化：

当然这里只是其中一个权重（运输矩阵的列的和），另一个权重（运输矩阵行的和）也可以用同样的方法得到。

08

Structured Fully Connected Layer

相信看了上面的这些，很多人会产生和我一样的疑惑：上面的方法看起来像是1 shot场景下的，只能一张support对应一张query求一个EMD分数。那么如何把它扩展到k shots下？

传统的FC可以看作是对每一个类找一个“原型向量”，进而我们可以用一些距离度量指标来分类。而SFC可以利用EMD，直接对结构化的特征表示进行分类。具体流程为：

09

Experiments

实验部分详见原文。

10

Conclusion

本文阅读难度中等。本文提出了利用EMD来进行度量学习，并且用cross-reference mechnism进行权重生成。SFC如何解决k shots的问题原文中写的并不是太清楚，需要一定的理解能力才能读懂这一部分。当然，从idea上来说，还是有一定的创新性的。以往小样本领域的EMD基本被用在数据分布修正上，基本是从数据流形的角度来优化分类。而这篇论文直接从图片本身出发，把EMD用作一种距离度量指标，这确实为一种可行的想法。

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！